import java.util.*;

public class 二叉树的锯齿形层序遍历 {
    public static int MAXN = 2001;
    public static int r,l;
    public static TreeNode[] queue = new TreeNode[MAXN];
    List<List<Integer>> ans;
    public boolean flag = true;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        r = l = 0;
        ans = new ArrayList<>();
        // 为空直接返回
        if (root == null) {
            return ans;
        }
        compute(root);
        return ans;
    }

    public void compute(TreeNode root) {
        queue[r++] = root; // 开始添加节点
        while (l < r) { // 广度优先遍历
            int size = r - l;
            List<Integer> list = new ArrayList<>();
            // // 先将元素添加进去, 通过 flag 来进行前后的遍历
            if (flag) {
                for (int i = l;i < r;i++) {
                    list.add(queue[i].val);
                }
            } else {
                for (int i = r - 1;i >= l;i--) {
                    list.add(queue[i].val);
                }
            }
            ans.add(list);
            while (size-- > 0) {
                TreeNode t = queue[l++];
                if (t.left != null) queue[r++] = t.left;
                if (t.right != null) queue[r++] = t.right;
            }
            flag = !flag;
        }
    }
}
